package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by 朱城委 on 2021-7-17.<br><br>
 *
 * 找到所有数组中消失的数字
 */
public class Topic448 {

    public static void main(String[] args) {
        Topic448 instance = new Topic448();

        int[] array = new int[] {4,3,2,7,8,2,3,1};
        System.out.println(instance.findDisappearedNumbers(array));

        array = new int[] {1, 1};
        System.out.println(instance.findDisappearedNumbers(array));
    }

    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> result = new ArrayList<>();

        for(int value : nums) {
            int index = (value - 1) % nums.length;
            nums[index] += nums.length;
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] <= nums.length) {
                result.add(i + 1);
            }
        }

        return result;
    }

    public List<Integer> findDisappearedNumbers3(int[] nums) {
        List<Integer> result = new ArrayList<>();

        for(int value : nums) {
            int index = Math.abs(value);
            nums[index - 1] = -Math.abs(nums[index - 1]);
        }

        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                result.add(i + 1);
            }
        }

        return result;
    }

    public List<Integer> findDisappearedNumbers2(int[] nums) {
        List<Integer> result = new ArrayList<>();

        int[] array = new int[nums.length];
        for(int value : nums) {
            array[value - 1]++;
        }

        for(int i = 0; i < array.length; i++) {
            if(array[i] == 0) {
                result.add(i + 1);
            }
        }

        return result;
    }
} 
